{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Gray Code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #math #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数学 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: grayCode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #格雷编码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<strong>n 位格雷码序列</strong> 是一个由 <code>2<sup>n</sup></code> 个整数组成的序列，其中：\n",
    "<ul>\n",
    "\t<li>每个整数都在范围 <code>[0, 2<sup>n</sup> - 1]</code> 内（含 <code>0</code> 和 <code>2<sup>n</sup> - 1</code>）</li>\n",
    "\t<li>第一个整数是 <code>0</code></li>\n",
    "\t<li>一个整数在序列中出现 <strong>不超过一次</strong></li>\n",
    "\t<li>每对 <strong>相邻</strong> 整数的二进制表示 <strong>恰好一位不同</strong> ，且</li>\n",
    "\t<li><strong>第一个</strong> 和 <strong>最后一个</strong> 整数的二进制表示 <strong>恰好一位不同</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> ，返回任一有效的 <strong>n 位格雷码序列</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>[0,1,3,2]\n",
    "<strong>解释：</strong>\n",
    "[0,1,3,2] 的二进制表示是 [00,01,11,10] 。\n",
    "- 0<strong><em>0</em></strong> 和 0<em><strong>1</strong></em> 有一位不同\n",
    "- <em><strong>0</strong></em>1 和 <em><strong>1</strong></em>1 有一位不同\n",
    "- 1<em><strong>1</strong></em> 和 1<em><strong>0</strong></em> 有一位不同\n",
    "- <em><strong>1</strong></em>0 和 <em><strong>0</strong></em>0 有一位不同\n",
    "[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。\n",
    "- <em><strong>0</strong></em>0 和 <em><strong>1</strong></em>0 有一位不同\n",
    "- 1<em><strong>0</strong></em> 和 1<em><strong>1</strong></em> 有一位不同\n",
    "- <em><strong>1</strong></em>1 和 <em><strong>0</strong></em>1 有一位不同\n",
    "- 0<em><strong>1</strong></em> 和 0<em><strong>0</strong></em> 有一位不同\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>[0,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 16</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [gray-code](https://leetcode.cn/problems/gray-code/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [gray-code](https://leetcode.cn/problems/gray-code/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n):\n",
    "        ans=[]\n",
    "        for i in range(1<<n):\n",
    "            ans.append(i^(i>>1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: 'int') -> 'List[int]':\n",
    "        if n == 0:\n",
    "            return [0]\n",
    "        if n == 1:\n",
    "            return [0, 1]\n",
    "        res = self.grayCode(n - 1)\n",
    "        base = 1\n",
    "        for i in range(n - 1):\n",
    "            base *= 2\n",
    "        for i in range(len(res) - 1, -1, -1):\n",
    "            res.append(res[i] + base)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if n == 0:\n",
    "            return [0]\n",
    "        res = []\n",
    "        def change(string,i):\n",
    "            if string[i] == '1':\n",
    "                string = string[:i] + '0' +string[i+1:]\n",
    "            else:\n",
    "                string = string[:i] + '1' +string[i+1:]\n",
    "            return string\n",
    "        string = '0' * n\n",
    "        d = {}\n",
    "        d[string] = 1\n",
    "        while(len(res) < 2**n):\n",
    "            res.append(int(string,2))\n",
    "            for i in range(n):\n",
    "                temp = change(string,i)\n",
    "                print(temp)\n",
    "                if temp in d:\n",
    "                    continue\n",
    "                else:\n",
    "                    d[temp] = 1\n",
    "                    string = temp\n",
    "                    break\n",
    "        return res\n",
    "                    \n",
    "        \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        resultCodeList = []\n",
    "        for i in range(0,2 ** n):\n",
    "            #print (i >> 1)\n",
    "            grayCode = (i >> 1)^i\n",
    "            \n",
    "            resultCodeList.append(grayCode)\n",
    "        return resultCodeList\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        self.isvisited=set()\n",
    "        self.res=[]\n",
    "        self.dfs(n,0)\n",
    "        return list(self.res)\n",
    "    def dfs(self,n,out):\n",
    "        self.res.append(out)\n",
    "        self.isvisited.add(out)\n",
    "        for i in range(n):\n",
    "            now=out\n",
    "            if now&(1<<i)==0:\n",
    "                now|=(1<<i)\n",
    "            else:\n",
    "                now&=~(1<<i)\n",
    "            if now in self.isvisited:\n",
    "                continue\n",
    "            self.dfs(n,now)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n):\n",
    "        def change(x):\n",
    "            if x == '0':\n",
    "                return '1'\n",
    "            else:\n",
    "                return '0'\n",
    "\n",
    "        def DFS(i, ans):\n",
    "            if i == 0:\n",
    "                return\n",
    "            for j in range(len(ans[-1])):\n",
    "                s = list(ans[-1])\n",
    "                s[j] = change(s[j])\n",
    "                s = ''.join(s)\n",
    "                if s not in ans:\n",
    "                    ans.append(s)\n",
    "                    DFS(i - 1, ans)\n",
    "        if n == 0:\n",
    "            return [0]\n",
    "        i = 2**n\n",
    "        res = []\n",
    "        ans = []\n",
    "        ans.append('0'*n)\n",
    "        DFS(i,ans)\n",
    "        for k in ans:\n",
    "            res.append(int(k,2))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: 'int') -> 'List[int]':\n",
    "        lens = pow(2, n)\n",
    "        res = []\n",
    "        ans = []\n",
    "        if n == 0:\n",
    "            return [0]\n",
    "        self.helper([0] * n, lens, res)\n",
    "        for i in res:\n",
    "            num = 0\n",
    "            for j in range(n):\n",
    "                num += i[n-(j+1)] * pow(2, j)\n",
    "            ans.append(num)\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "    def helper(self, code, lens, res):\n",
    "        if len(res) == lens:\n",
    "            return\n",
    "        if code not in res:\n",
    "            res.append(copy.deepcopy(code))\n",
    "            self.helper(code, lens, res)\n",
    "            return\n",
    "        for i in range(len(code)):\n",
    "            code[i] = int(not code[i])\n",
    "            if code not in res:\n",
    "                self.helper(code, lens, res)\n",
    "                break\n",
    "            code[i] = int(not code[i])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: 'int') -> 'List[int]':\n",
    "        #https://blog.csdn.net/grape875499765/article/details/79201193\n",
    "        res = [0]\n",
    "        for i in range(n):\n",
    "            temp = 1 << i\n",
    "            for j in range(len(res)-1, -1, -1):\n",
    "                res.append(res[j] + temp)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        head ,res=1, [0]\n",
    "        for i in range(n):\n",
    "            for j in range(len(res)-1,-1,-1):\n",
    "                res.append(head+res[j])\n",
    "            head<<=1\n",
    "        return res        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        if (n==0):\n",
    "            return [0]\n",
    "        elif (n==1):\n",
    "            return [0,1]\n",
    "        base = ['0','1']\n",
    "        for i in range(1,n):\n",
    "            seq = []\n",
    "            for j,s in enumerate(base):\n",
    "                if (j%2==0):\n",
    "                    seq.append(s+'0')\n",
    "                    seq.append(s+'1')\n",
    "                elif (j%2==1):\n",
    "                    seq.append(s+'1')\n",
    "                    seq.append(s+'0')\n",
    "            base = seq\n",
    "        for i,kk in enumerate(base):\n",
    "            base[i] = int(base[i],2)\n",
    "        return base\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        dp=[0]\n",
    "        for i in range(1,n+1):\n",
    "            dp+=[(x+2**(i-1)) for x in dp[::-1]]\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        res, head = [0], 1\n",
    "        for _ in range(n):\n",
    "            lengths = len(res)\n",
    "            for i in range(lengths-1, -1, -1):\n",
    "                res.append(head+res[i])\n",
    "            head <<= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        \n",
    "        # if n == 0:\n",
    "        #     return [0]\n",
    "\n",
    "        # i ^ i >> 1 ：自己与自己左移一位进行异或，得到的就是它的格雷码\n",
    "        return [i ^ i >> 1  for i in range(2 ** n)]\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        gray_codes = []\n",
    "        trace = []\n",
    "        \n",
    "        def decode(gray_codes):\n",
    "            res = []\n",
    "            for gray_code in gray_codes:\n",
    "                decimal = 0\n",
    "                for bit in gray_code:\n",
    "                    decimal = decimal * 2 + bit\n",
    "                res.append(decimal)\n",
    "            return res\n",
    "        \n",
    "        def backtrack(choice_list=(0, 1)):\n",
    "            if len(trace) == n:\n",
    "                gray_codes.append(trace[:])\n",
    "                return\n",
    "            else:\n",
    "                should_toggle = False\n",
    "                for code in choice_list:\n",
    "                    trace.append(code)\n",
    "                    if should_toggle:\n",
    "                        backtrack((1,0))\n",
    "                    else:\n",
    "                        backtrack((0,1))\n",
    "                        should_toggle = True\n",
    "                    trace.pop()\n",
    "        backtrack()\n",
    "        return decode(gray_codes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        def getNear(snum,idx):\n",
    "            if snum[idx]=='0':\n",
    "                c='1'\n",
    "            else:\n",
    "                c='0'\n",
    "            return snum[0:idx]+c+snum[idx+1:]\n",
    "\n",
    "        def getCodeStr(n,clen):\n",
    "            res=[]\n",
    "            while n:\n",
    "                res.insert(0,str(n%2))\n",
    "                n=n//2\n",
    "            # print(res)\n",
    "            return '0'*(clen-len(res))+''.join(res)\n",
    "\n",
    "        # print(getCodeStr(3,4))\n",
    "        if n==0:\n",
    "            return [0]\n",
    "        ncode=[]\n",
    "        dcode={}\n",
    "        nlen=2**n\n",
    "        for x in range(nlen):\n",
    "            ncode.append(getCodeStr(x,n))\n",
    "            dcode[ncode[-1]]=x\n",
    "        # print(dcode)\n",
    "\n",
    "        stp={0:[ncode[0]]}\n",
    "        que=[0]\n",
    "        q2={ncode[0]:0}\n",
    "        # ncode=ncode[1:]\n",
    "        i=1\n",
    "        while i>0 and i<nlen:\n",
    "            if i not in stp:\n",
    "                for x in range(n):\n",
    "                    cd = getNear(stp[i-1][0],x)\n",
    "                    if cd not in q2:\n",
    "                        stp[i]=[cd]\n",
    "                        que.append(dcode[cd])\n",
    "                        q2[cd]=x\n",
    "                        break\n",
    "\n",
    "                if i in stp:\n",
    "                    # ncode.pop(ncode.index(stp[i][0]))\n",
    "                    i+=1\n",
    "                else:\n",
    "                    i-=1\n",
    "            else:\n",
    "                # ncode.append(stp[i].pop(0))\n",
    "                t=que.pop()\n",
    "                cd=stp[i].pop()\n",
    "                st=q2[cd]\n",
    "                for x in range(st+1,n):\n",
    "                    cd = getNear(stp[i-1][0],x)\n",
    "                    if cd not in q2:\n",
    "                        stp[i]=[cd]\n",
    "                        que.append(dcode[cd])\n",
    "                        q2[cd]=x\n",
    "                        break\n",
    "                if stp[i]:\n",
    "                    i+=1\n",
    "                else:\n",
    "                    del stp[i]\n",
    "                    i-=1\n",
    "\n",
    "            # print(i,stp)\n",
    "\n",
    "        if i==nlen:\n",
    "            return que\n",
    "        else:\n",
    "            return []\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        res = [0]\n",
    "        head = 1\n",
    "        for i in range(n):\n",
    "            for j in range(len(res)-1,-1,-1):\n",
    "                res.append(head+res[j])\n",
    "            head <<= 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        ret = []\n",
    "        for i in range(pow(2, n)):\n",
    "            ret.append(i ^ i >> 1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dp = {\n",
    "        0: ['0'],\n",
    "        1: ['0', '1']\n",
    "    }\n",
    "\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        ret = self.grayCodeBin(n)\n",
    "        ret = [int(i, 2) for i in ret]\n",
    "        return ret\n",
    "    \n",
    "    def grayCodeBin(self, n: int):\n",
    "        if n in Solution.dp.keys():\n",
    "            return Solution.dp[n]\n",
    "\n",
    "        tmp = self.grayCodeBin(n - 1)\n",
    "        preHalf = ['0' + i for i in tmp]\n",
    "        lastHalf = ['1' + i for i in tmp[::-1]]\n",
    "        ret = preHalf + lastHalf\n",
    "        Solution.dp[n] = ret\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        if n==0:\n",
    "            return [0]\n",
    "\n",
    "        def backTrack(index,seq):\n",
    "            if index==n:\n",
    "                res.append(oneSample[:])\n",
    "                return\n",
    "            \n",
    "            bit=[0,1] if seq%2==0 else [1,0]\n",
    "\n",
    "            for i in range(len(bit)):\n",
    "                oneSample.append(str(bit[i]))\n",
    "                backTrack(index+1,i)\n",
    "                oneSample.pop()\n",
    "        \n",
    "        oneSample=list()\n",
    "        res=list()\n",
    "        backTrack(0,0)\n",
    "\n",
    "        intans=[int(''.join(x),2) for x in res]\n",
    "\n",
    "        return intans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        def backtrack(current: int) -> bool:\n",
    "            if len(result) == 1 << n:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                next_num = current ^ (1 << i)\n",
    "                if next_num not in result_set:\n",
    "                    result.append(next_num)\n",
    "                    result_set.add(next_num)\n",
    "                    if backtrack(next_num):\n",
    "                        return True\n",
    "                    result.pop()\n",
    "                    result_set.remove(next_num)\n",
    "            return False\n",
    "\n",
    "        result = [0]\n",
    "        result_set = {0}\n",
    "        backtrack(0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n):\n",
    "        if n == 0:\n",
    "            return [0]\n",
    "\n",
    "        tmp_list = ['0'] * n\n",
    "        gray_set = set()\n",
    "        \n",
    "        # 递归求解\n",
    "        def recur(tmp_list):\n",
    "            tmp = ''.join(tmp_list)\n",
    "            # 如果当前格雷码没出现过，就加入解集\n",
    "            if tmp not in gray_set:\n",
    "                gray_set.add(tmp)\n",
    "                res.append(int(tmp, 2))\n",
    "            # 如果找到所有解，就返回\n",
    "            if len(res) == 2 ** n:\n",
    "                return\n",
    "            # 对当前格雷码，尝试构造出邻接着它的下一个格雷码,具体做法是从低到高去翻转一位\n",
    "            for i in range(n):\n",
    "                # 只翻转一位\n",
    "                tmp_list = reverse(tmp_list, i)\n",
    "                tmp = ''.join(tmp_list)\n",
    "                # 如果翻转该位之后可以构成解，则进行递归\n",
    "                if tmp not in gray_set:\n",
    "                    recur(tmp_list)\n",
    "                # 否则，如果翻转某位之后，得到的格雷码已经在集合里，则将该位翻转回来\n",
    "                # 然后进行下一位的翻转\n",
    "                else:\n",
    "                    tmp_list = reverse(tmp_list, i)       \n",
    "        # 辅助函数，用于翻转该位数字\n",
    "        def reverse(tmp_list, idx):\n",
    "            if tmp_list[idx] == '0':\n",
    "                tmp_list[idx] = '1'\n",
    "            else:\n",
    "                tmp_list[idx] = '0'\n",
    "            return tmp_list\n",
    "\n",
    "        res = []\n",
    "        recur(tmp_list)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        path = []\n",
    "        visited = [False] * pow(2, n)\n",
    "        if self.search(n, path, visited):\n",
    "            return path\n",
    "\n",
    "    def search(self, n, path, visited):\n",
    "        if not path:\n",
    "            path.append(0)\n",
    "            visited[0] = True\n",
    "            return self.search(n, path, visited)\n",
    "        if len(path) == pow(2, n):\n",
    "            return True\n",
    "        lastNum = path[-1]\n",
    "        bits = bin(lastNum)[2:]\n",
    "        bits = (n - len(bits)) * '0' + bits\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if bits[i] == '1':\n",
    "                num = lastNum - pow(2, n - 1 - i)\n",
    "                if visited[num] == False:\n",
    "                    visited[num] = True\n",
    "                    path.append(num)\n",
    "                    if self.search(n, path, visited):\n",
    "                        return True\n",
    "                    path.pop()\n",
    "                    visited[num] = False\n",
    "            if bits[i] == '0':\n",
    "                num = lastNum + pow(2, n - 1 - i)\n",
    "                if visited[num] == False:\n",
    "                    visited[num] = True\n",
    "                    path.append(num)\n",
    "                    if self.search(n, path, visited):\n",
    "                        return True\n",
    "                    path.pop()\n",
    "                    visited[num] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        '''\n",
    "        给定n后，就定了总长度是2^n，这些数字都要出现\n",
    "        然后每次可以往邻居方向走，但是问题是必须是一笔画完，但是我试了试，好像总是死不了\n",
    "        '''\n",
    "        if not n:\n",
    "            return [0]\n",
    "        vis=collections.defaultdict(int)\n",
    "        res=[]\n",
    "        \n",
    "        def nei(s):\n",
    "            neis=[]\n",
    "            temp=list(s)\n",
    "            for i in range(len(s)):\n",
    "                temp[i]='0' if temp[i]=='1' else '1'\n",
    "                neis.append(''.join(temp))\n",
    "                temp[i]='0' if temp[i]=='1' else '1'\n",
    "            return neis\n",
    "        def dfs(curn):\n",
    "            vis[curn]=1\n",
    "            res.append(curn)\n",
    "            # print(curn)\n",
    "            # print(nei(curn))\n",
    "            for nextn in nei(curn):\n",
    "                if not vis[nextn]:\n",
    "                    # res.append(nextn)\n",
    "                    dfs(nextn)\n",
    "        dfs('0'*n)\n",
    "        print(res)\n",
    "        return list(map(lambda x:int(x,2),res))\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        seen = set([0])\n",
    "        def backtrack(path):\n",
    "            if len(path) == 2 ** n: return path\n",
    "            for i in range(n):\n",
    "                nxt = 1 << i ^ path[-1]\n",
    "                if nxt in seen: continue\n",
    "                seen.add(nxt)\n",
    "                path.append(nxt)\n",
    "                if backtrack(path): return path\n",
    "                path.pop()\n",
    "                seen.remove(nxt)\n",
    "        return backtrack([0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        if n is 0:\n",
    "            return [0]\n",
    "        elif n is 1:\n",
    "            return [0, 1]\n",
    "\n",
    "        def code_to_num(code: str):\n",
    "            num = 0\n",
    "            for digit in code:\n",
    "                num = (num << 1) + (ord(digit) - ord('0'))\n",
    "            return num\n",
    "\n",
    "        def num_to_code(num: int):\n",
    "            code = \"\"\n",
    "            for i in range(n):\n",
    "                code = str(num % 2) + code\n",
    "                num = num >> 1\n",
    "            return code\n",
    "\n",
    "        def get_next_gray_code_list(code: str):\n",
    "            result = []\n",
    "            for i in range(len(code)):\n",
    "                result.append(code[:i] + str(ord('1') - ord(code[i])) + code[i+1:])\n",
    "            return result\n",
    "\n",
    "        record = []\n",
    "        used_set = set()\n",
    "\n",
    "        def search(code: str):\n",
    "            if code in used_set:\n",
    "                return\n",
    "            else:\n",
    "                used_set.add(code)\n",
    "                record.append(code_to_num(code))\n",
    "                for next_code in get_next_gray_code_list(code):\n",
    "                    search(next_code)\n",
    "\n",
    "        search(num_to_code(0))\n",
    "        return record"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.r = None\n",
    "        \n",
    "    def div(self, n):\n",
    "        if n == 0:\n",
    "            self.r = [0]\n",
    "            return\n",
    "        dl = pow(2,n)\n",
    "        d = list(range(dl//2, dl))\n",
    "        for i in range((dl//2)-1, -1, -1):\n",
    "            self.r.append(d[self.r[i]])\n",
    "            \n",
    "    def grayCode(self, n):\n",
    "        for i in range(n+1):\n",
    "            self.div(i)\n",
    "        return self.r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        ans = [0] * (1 << n)\n",
    "        for i in range(1 << n):\n",
    "            ans[i] = (i >> 1) ^ i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "\n",
    "        gray = [i ^ i >> 1 for i in range(1 << n)]\n",
    "        return gray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0,1]\n",
    "        left = self.grayCode(n-1)\n",
    "        right = left.copy()\n",
    "        right.reverse()\n",
    "        right = [x + (1<<(n-1)) for x in right]\n",
    "        return left + right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        if n == 0:\n",
    "            return [0]\n",
    "        prefix = 1 << (n-1)\n",
    "        codes = self.grayCode(n-1)\n",
    "        return codes + [prefix | _ for _ in reversed(codes)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        if n == 1: return [0, 1]\n",
    "        ans = self.grayCode(n - 1)\n",
    "        reans = ans.copy()\n",
    "        reans.reverse()\n",
    "        # return [num << 1 for num in ans] + [num << 1 | 1 for num in reans]\n",
    "        return ans + [1 << (n - 1) | num for num in reans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(1 << n):\n",
    "            res.append(i ^ (i >> 1))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        gray_seq = [0]\n",
    "\n",
    "        for i in range(n):\n",
    "            size = 2 ** i\n",
    "            reversed_seq = gray_seq[::-1]\n",
    "            gray_seq += [num + size for num in reversed_seq]\n",
    "\n",
    "        return gray_seq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "\n",
    "        def DFS(nx: int) -> List[int]:\n",
    "            if nx == 1:\n",
    "                return [0, 1]\n",
    "            #\n",
    "            nums = DFS(nx - 1)\n",
    "            ret = []\n",
    "            for i, num in enumerate(nums):\n",
    "                if i % 2 == 0:  # 逐一交替，添加0/1或1/0\n",
    "                    ret.append(num * 2)\n",
    "                    ret.append(num * 2 + 1)\n",
    "                else:\n",
    "                    ret.append(num * 2 + 1)\n",
    "                    ret.append(num * 2)\n",
    "            return ret\n",
    "        #\n",
    "        return DFS(n)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        if n == 1: return [0, 1]\n",
    "        ans = self.grayCode(n - 1)\n",
    "        reans = ans.copy()\n",
    "        reans.reverse()\n",
    "        ans = [num << 1 for num in ans] + [num << 1 | 1 for num in reans]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        res = [0,1]\n",
    "        def dg(a,b):\n",
    "            if a == 2**n:\n",
    "                return\n",
    "            add = [a,*[-i for i in b[::-1]]]\n",
    "            for i in add:\n",
    "                res.append(res[-1]+i)\n",
    "            dg(a*2,[*b,*add])\n",
    "        dg(2,[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        s = [\"0\",\"1\"]\n",
    "        for i in range(1,n):\n",
    "            l = len(s)\n",
    "            for j in range(l):\n",
    "                s[j]= \"0\"+s[j]\n",
    "            for j in range(l-1,-1,-1):\n",
    "                s.append(\"1\"+s[j][1:])\n",
    "        for i in range(len(s)):\n",
    "            s[i] = int(s[i],2) \n",
    "        return  s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        if n==0:    return [0]\n",
    "        res = []\n",
    "        def back(now, x):\n",
    "            if len(now)==n:\n",
    "                res.append(int(now, 2))\n",
    "            elif x==0:\n",
    "                back(now+'0',0)\n",
    "                back(now+'1',1)\n",
    "            else:\n",
    "                back(now+'1',0)\n",
    "                back(now+'0',1)\n",
    "        back('',0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        if n==0:\n",
    "            return [0]\n",
    "\n",
    "        res=[]\n",
    "        def back(now,x):\n",
    "            if len(now)==n:\n",
    "                res.append(int(now,2))\n",
    "            elif x==0:\n",
    "                back(now+'0',0)\n",
    "                back(now+'1',1)\n",
    "            else:\n",
    "                back(now+'1',0)\n",
    "                back(now+'0',1)\n",
    "        \n",
    "        back('',0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        tree = ['0','1']\n",
    "        res = [0,1]\n",
    "        for _ in range(2, n + 1):\n",
    "            for b in tree[::-1]:\n",
    "                tree.append('1'+b)\n",
    "                res.append(int('1'+b,2))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @functools.cache\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        if n==1:\n",
    "           return [0,1]\n",
    "        else:\n",
    "            res=self.grayCode(n-1)\n",
    "            return res+[pow(2,n-1)+i for i in res[::-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        left_tree = ['0']\n",
    "        right_tree = ['1']\n",
    "        for _ in range(2, n + 1):\n",
    "            lt = []\n",
    "            rt = []\n",
    "            for b in left_tree + right_tree:\n",
    "                lt.append(b)\n",
    "                rt.append('1' + b)\n",
    "            left_tree = lt\n",
    "            right_tree = rt[::-1]\n",
    "        return [int(num, 2) for num in left_tree + right_tree]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        ans = []\n",
    "        s = [\"0\"]*n\n",
    "        def dfs(s, i):\n",
    "            if i==n:\n",
    "                ans.append(\"\".join(s))\n",
    "                return\n",
    "            dfs(s, i+1)\n",
    "            s[i]='1' if s[i] == '0' else '0'\n",
    "            dfs(s, i+1)\n",
    "        dfs(s, 0)\n",
    "        ans = list(map(lambda x: int(x, 2), ans))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "\n",
    "        def two_steps(strs):\n",
    "            strs = list(strs)\n",
    "            x1=''\n",
    "            x2=''\n",
    "            for i in range(len(strs)-1,-1,-1):\n",
    "                if i==len(strs)-1:\n",
    "                    strs[i] = '1' if strs[i]=='0' else '0'\n",
    "                    x1 = ''.join(strs)\n",
    "                    if strs[i]=='1' and i>0:\n",
    "                        strs[i-1] = '1' if strs[i-1]=='0' else '0'\n",
    "                        x2 = ''.join(strs)\n",
    "                        return [x1,x2]\n",
    "                elif strs[i]=='1' and i>0:\n",
    "                    strs[i - 1] = '1' if strs[i - 1] == '0' else '0'\n",
    "                    x2 = ''.join(strs)\n",
    "                    return [x1, x2]\n",
    "\n",
    "            return [x1]\n",
    "\n",
    "        result=[n*'0']\n",
    "        while len(result) < 2**n :\n",
    "            result=result+two_steps(result[-1])\n",
    "        result = [int(x,2) for x in result]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        res=['0','1']\n",
    "        for i in range(1,n):\n",
    "            length = len(res)\n",
    "            for j in range(length-1,-1,-1):\n",
    "                res.append('1'+res[j])\n",
    "            for j in range(length):\n",
    "                res[j]='0'+res[j]\n",
    "        return [int(i,2) for i in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        def graystr(n):\n",
    "            if n == 1:\n",
    "                return ['0', '1']\n",
    "            \n",
    "            re = []\n",
    "            sub1 = graystr(n-1)\n",
    "            for i in range(len(sub1)):\n",
    "                re.append('0'+sub1[i])\n",
    "            for i in range(len(sub1)):\n",
    "                re.append('1'+sub1[len(sub1)-1-i])\n",
    "            return re\n",
    "        \n",
    "        re = graystr(n)\n",
    "        for i in range(len(re)):\n",
    "            re[i] = int(re[i], 2)\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0,1]\n",
    "        res = deque()\n",
    "        res.append(\"\")\n",
    "        for _ in range(0, n):\n",
    "            l = len(res)\n",
    "            for ll in range(l):\n",
    "                cur = res.popleft()\n",
    "                if ll % 2 == 0:\n",
    "                    res.append(cur+\"0\")\n",
    "                    res.append(cur+\"1\")\n",
    "                else:\n",
    "                    res.append(cur+\"1\")\n",
    "                    res.append(cur+\"0\")\n",
    "        return [int(n,2) for n in list(res)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        gray_code_binary = self.grayCodeBinary(n)\n",
    "        return [int(item, 2) for item in gray_code_binary]\n",
    "\n",
    "    def grayCodeBinary(self, n):\n",
    "        if n == 1:\n",
    "            return [\"0\", \"1\"]\n",
    "\n",
    "        gray_code_binary = self.grayCodeBinary(n-1)\n",
    "        result = []\n",
    "        for item in gray_code_binary:\n",
    "            result.append(\"0\" + item)\n",
    "        for item in gray_code_binary[::-1]:\n",
    "            result.append(\"1\" + item)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        def verse(level: int):\n",
    "            if level == 1:\n",
    "                return [\"0\", \"1\"]\n",
    "            result_sub = verse(level - 1)\n",
    "            result = [\"0\"+ i for i in result_sub] + [\"1\" + i for i in result_sub[::-1]]\n",
    "            return result\n",
    "        sol = verse(n)\n",
    "        sol = [eval(\"0b\"+i) for i in sol]\n",
    "        return sol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        ll = ['0', '1']\n",
    "        for i in range(1, n):\n",
    "            temp = []\n",
    "            for ele in ll:\n",
    "                temp.append('0' + ele)\n",
    "            for ele in ll[::-1]:\n",
    "                temp.append('1' + ele)\n",
    "            ll = temp[:]\n",
    "        res = []\n",
    "        for s in ll:\n",
    "            res.append(int(s, 2))\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
